package leetcode.Fiftyone_to_One_hundred;

import java.util.ArrayList;
import java.util.List;

/**
 * 子集
 * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
 *
 * 说明：解集不能包含重复的子集。
 */
public class Test78 {

    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<>());

        // 求子集无非就是求长度为0的子集，长度为1的、2的。。一直到nums的最大长度也就是原集
        for (int i = 1; i <= nums.length; i++) {
            dp(ans, new ArrayList<>(), nums, i, 0);
        }

        return ans;
    }

    public static void dp(List<List<Integer>> ans, List<Integer> temp,
                          int[] nums, int t, int index) {
        // 用 t 来控制当前需要的子集的长度
        if (temp.size() == t) {
            ans.add(new ArrayList<>(temp));
        } else {
            for (int i = index; i < nums.length; i++) {
                if (temp.contains(nums[i]))
                    continue;
                temp.add(nums[i]);
                dp(ans, temp, nums, t, i);
                temp.remove(temp.size() - 1);
            }
        }

    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(subsets(nums));
    }
}
